#define  _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    bool isMatch(string s, string p) {
        int s_size = s.size(), p_size = p.size();
        vector<vector<bool>> dp(s_size + 1, vector<bool>(p_size + 1));
        dp[0][0] = true;
        s = ' ' + s;
        p = ' ' + p;
        for (int i = 2; i <= p_size; i += 2)
            if (p[i] == '*') dp[0][i] = true;
            else break;
        for (int i = 1; i <= s_size; i++)
            for (int j = 1; j <= p_size; j++)
                if (p[j] == '.' || s[i] == p[j])
                    dp[i][j] = dp[i - 1][j - 1];
                else if (p[j] == '*')
                    dp[i][j] = dp[i][j - 2] || (p[j - 1] == '.' || p[j - 1] == s[i]) && dp[i - 1][j];
        return dp[s_size][p_size];
    }
};